#define  _CRT_SECURE_NO_WARNINGS 1
void QueueInit(Queue* p)
{
	assert(p);
	p->Phead = p->tail = NULL;
	p->size = 0;
}

void QueueDestroy(Queue* p)
{
	assert(p);
	Node* cur = p->Phead;
	while (cur)
	{
		Node* next = cur->next;
		free(cur);
		cur = next;
	}
	p->Phead = p->tail = NULL;
	p->size = 0;
}
void Qpush(Queue* p, QDataType X)
{
	assert(p);
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->x = 0;
	if (p->Phead == NULL)
	{
		p->Phead = p->tail = newNode;
	}
	else {
		p->tail->next = newNode;
		p->tail = newNode;
	}
	p->size++;
}

QDataType QFront(Queue* p)
{
	assert(p);
	assert(p->Phead);
	return p->Phead->x;
}

void Qpop(Queue* p)
{
	assert(p);
	assert(p->size);
	if (p->Phead->next = NULL)
	{
		free(p->Phead);
		p->Phead = p->tail = NULL;
	}
	else
	{
		Node* next = p->Phead->next;
		free(p->Phead);
		p->Phead = next;
	}
	p->size--;
}


bool QueueEmpty(Queue* p)
{
	assert(p);
	if (p->size == 0)
		return true;
	else
		return false;
}



void TreeLevelInorder(BTNode* root)
{
	Queue p;
	QueueInit(&p);
	if (root)
	{
		Qpush(&p, root);
	}
	while (!QueueEmpty(&p))
	{
		BTNode* Front = QFront(&p);
		Qpop(&p);
		printf("%d", Front->data);
		if (Front->left)
			Qpush(&p, Front->left);
		if (Front->right)
			Qpush(&p, Front->right);
	}
	QueueDestroy(&p);
}

bool TreeComplete(BTNode* root)
{
	Queue p;
	QueueInit(&p);
	if (root != NULL)
	{
		Qpush(&p, root);
	}

	while (!QueueEmpty(&p))
	{
		BTNode* Front = QFront(&p);
		Qpop(&p);
		if (Front == NULL)
		{
			break;
		}
		Qpush(&p, Front->left);
		Qpush(&p, Front->right);
	}
	while (!QueueEmpty(&p))//From here on,it should all be empty
	{
		BTNode* front = QFront(&p);
		Qpop(&p);
		if (front)//can only be empty, cannot exist
		{
			QueueDestroy(&p);
			return false;
		}
	}
	QueueDestroy(&p);
	return true;
}


void Insertsort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				a[end + 1] = tmp;
				break;
			}
			if (end == -1)
			{
				a[end + 1] = tmp;
				break;
			}
		}
	}
}
